1337. The K Weakest Rows in a Matrix

1. Question

You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:

The number of soldiers in row iis less than the number of soldiers in rowj. Both rows have the same number of soldiers andi < j. Return the indices of thek weakest rows in the matrix ordered from weakest to strongest.

2. Examples

Example 1:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 

- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
  The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

nput: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers in each row is: 

- Row 0: 1 
- Row1: 4 
- Row 2: 1 
- Row 3: 1 
  The rows ordered from weakest to strongest are [0,2,3,1].

3. Constraints

• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100 1 <= k <= m matrix[i][j] is either 0 or 1.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        if(null == mat || 0 == mat.length || 0 == mat[0].length || 0 == k){
            return null;
        }
        int[][] res = new int[mat.length][2];
        for(int i = 0; i < mat.length; i++){
            res[i][0] = i;
            res[i][1] = binarySearch(mat[i]);
        }

        Arrays.sort(res, (a, b) -> a[1] - b[1]);
        int[] arr = new int[k];
        for(int i = 0; i < k; i++){
            arr[i] = res[i][0];
        }

        return arr;

    }

    public static int binarySearch(int[] arr){
        if(0 == arr[0])return 0;
        if(1 == arr[arr.length-1])return arr.length;
        int left = 0;
        int right = arr.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(0 == arr[mid] && 1 == arr[mid-1]){
                return mid;
            }else if( 0 == arr[mid] ){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}